package com.wtgroup.demo.mianshi.算法.字符串.字符串匹配;

import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Sout;

/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/20 14:26
 */
public class D_KMP {
    public static void main(String[] args) {
        Judger.of(() -> {
            String str = RandomUtil.randomString(RandomUtil.BASE_KEY_BOARD, RandomUtil.randomInt(0, 40));
            String pattern = RandomUtil.randomString(RandomUtil.BASE_KEY_BOARD, RandomUtil.randomInt(0, 40));
            int res1 = D_KMP.func(str, pattern);
            int res2 = D_暴力.match(str, pattern);
            if (res1 != res2) {
                Sout.println(res1, res2, str, pattern);
            }
            return res1 == res2;
        }).setIterCount(10).start().print();
    }

    //  先简单, 不考虑已经匹配过的前缀部分. 只是在暴力基础上, 失败时, 往后跳跃式推进, 不是往后不定移动一位继续暴力匹配.
    static int func(String str, String pattern) {
        int N1 = str.length(), N2 = pattern.length();
        int[] nexts = getNexts(pattern);

        for (int i = 0; i <= N1 - N2; ) {
            boolean matched = true;
            for (int j = 0; j < N2; j++) {
                if (pattern.charAt(j) != str.charAt(i + j)) {
                    // 往前回退, 也可看成 i 位置往后跳跃推移.
                    i = i + j - nexts[j];
                    matched = false;
                    break;
                }
            }
            if (matched) {
                return i;
            }
        }

        return -1;
    }

    private static int[] getNexts(String pattern) {
        int[] nexts = new int[pattern.length()];
        if (pattern.length() == 0) {
            return nexts;
        }
        nexts[0] = -1;
        if (pattern.length() < 2) {
            return nexts;
        }
        nexts[1] = 0;

        for (int i = 2; i < pattern.length(); i++) {
            // i-1 和 对应 nexts[i-1] 位对比
            int p = nexts[i - 1]; // 待比较位置
            char val_i1 = pattern.charAt(i - 1);
            while (p >= 0) {
                if (val_i1 == pattern.charAt(p)) {
                    nexts[i] = p + 1;
                    break;
                }
                // 继续向前跳
                p = nexts[p];
            }
        }

        return nexts;
    }


}
